package DP.Leetcode;

import java.util.Scanner;

/**
 * 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。n<=39
 */
public class Fibonacci {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入n：");
        int n = sc.nextInt();
        System.out.println(Fibonacci2(n));


    }

    /**
     * 递归写法，当n非常大时，就会非常耗时
     * @param n
     * @return
     */
        public static  int Fibonacci(int n) {

            if(n==0){
                return 0;
            }
            if(n==1){
                return 1;
            }
            return Fibonacci(n-1)+Fibonacci(n-2);
        }

    /**
     * 数组写法
     * @param n
     * @return
     */
        public static  int Fibonacci1(int n){
            if (n==0){
                return 0;
            }
            if (n==1){
                return 1;
            }
            int[] arr=new int[n+1];
            arr[0]=0;
            arr[1]=1;
            for (int i = 2; i <n+1; i++) {
                arr[i]=arr[i-1]+arr[i-2];
            }
            return arr[n];
        }

    /**
     * 使用变量优化
     * @param n
     * @return
     */
    public static int Fibonacci2(int n){
        if (n==0){
            return 0;
        }
        if (n==1){
            return 1;
        }
        int fn=0;
        int f1=1;
        int f2=0;
        for (int i = 2; i <n+1; i++) {
            fn=f1+f2;
            f2=f1;
            f1=fn;
        }
        return fn;
        }

}